/**
 * 最大公约数
 */
public class CommonDivisor {

    public static void main(String[] args) {
        System.out.println("Common Divisor: " + nthMagicalNumber(1000000000, 40000, 40000));
    }

    /**
     * 最小公约数： 时间复杂度 (logA)^3
     * @param a
     * @param b
     * @return
     */
    public static long gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    /**
     * 最大公约数
     * @param a
     * @param b
     * @return
     */
    public static long lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    /**
     * <a href="https://leetcode.cn/problems/nth-magical-number/">第N个神奇的数</a>
     */
    public static long nthMagicalNumber(int n, int a, int b) {
        long lcm = lcm(a, b);
        long ans = 0;

        for (long l = 0, r = (long) n * Math.min(a, b), m; l <= r;) {
            m = (l + r) / 2;
            long count = m / a + m / b - m / lcm;
            if (count >= n) {
                r = m - 1;
                ans = m;
            } else {
                l = m + 1;
            }
        }
        return ans % ((int)1e9 + 7);
    }

}
